#define _CRT_SECURE_NO_WARNINGS 1
int PartSort2(int* a, int left, int right)
{
	// 使用三数取中法获取基准元素的正确位置
	int Mid = GetMidi(a, left, right);
	// 将基准元素交换到数组的最左边
	Swap(&a[left], &a[Mid]);

	// 把基准值保存到临时变量key中
	int key = a[left];
	// 将基准值的下标保存到临时变量hole（坑位）中
	int hole = left;

	// 当left小于right时，进行单趟排序
	while (left < right)
	{
		// 从右向左扫描，找到第一个小于基准元素的值
		while (left < right && a[right] >= key)
		{
			--right;
		}
		// 将找到的元素放到"坑"中
		a[hole] = a[right];
		// 更新"坑"的位置
		hole = right;

		// 从左向右扫描，找到第一个大于基准元素的值
		while (left < right && a[left] <= key)
		{
			++left;
		}
		// 将找到的元素放到"坑"中
		a[hole] = a[left];
		// 更新"坑"的位置
		hole = left;
	}

	// 最后，将基准元素放到正确的位置（hole此时指向的位置）
	a[hole] = key;
	// 返回基准元素的最终位置
	return hole;
}